package xyz.vopen.leetcode.q84;

import java.util.Stack;

/**
 * {@link ElveXu}
 *
 * @author <a href="mailto:iskp.me@gmail.com">Elve.Xu</a>
 * @version ${project.version} - 2020-05-04.
 */
public class ElveXu {
    public int largestRectangleArea(int[] heights) {
    Stack<Integer> stack = new Stack<>();
    int[] left =  leftBound(heights, stack);
    int[] right = rightBound(heights, stack);
    int result = 0;
    for (int i = 0 ; i < heights.length;  i++)
      result = Math.max(result, heights[i] * (right[i] - left[i] + 1));

    return result;
  }

  public int[] rightBound(int[] h, Stack<Integer> stack){
    int[] bound = new int[h.length];
    stack.clear();
    for (int i = h.length - 1 ; i >= 0 ; i--){
      while(!stack.isEmpty() && h[stack.peek()] >= h[i]) stack.pop();
      bound[i] = stack.isEmpty() ? h.length - 1 : stack.peek() - 1;
      stack.push(i);
    }
    return bound;
  }

  public int[] leftBound(int[] h, Stack<Integer> stack){
    int[] bound = new int[h.length];
    stack.clear();
    for (int i = 0 ; i < h.length ; i++){
      while(!stack.isEmpty() && h[stack.peek()] >= h[i]) stack.pop();
      bound[i] = stack.isEmpty() ? 0 : stack.peek() + 1;
      stack.push(i);
    }
    return bound;
  }
}
